import java.util.Scanner;

public class HashTab<V> {
    private Tab data;
    private final int M = 31;

    public static void main(String[] args){
        HashTab<String> hashTab = new HashTab<>();
        Scanner s = new Scanner(System.in);
        String[] names = {
                "fujie",
                "qiannan",
                "liuzheng",
                "heqiong",
                "pengyingying",
                "jilong",
                "wangzhe",
                "liujun",
                "zhangchao",
                "zuoliwei",
                "zhanglei",
                "madingding"
        };
        for(String string : names){
            hashTab.add(string,string);
        }
        System.out.print("请输入要查询的姓名：");
        System.out.println(hashTab.get(s.nextLine()));
        s.close();
    }

    public HashTab(){
        data = new Tab();
    }
    private int hashFun(String key){
        //除留余数法计算散列地址
        int hash = 0;

        int hashbase = 0; //用于在二次探测中记录基础散列地址
        int f = 1; //用于在二次探测中控制符号
        for(int i = 0; i < key.length(); i++){
            hash = (key.charAt(i) + hash) % M;
        }
        hashbase = hash;
        //处理冲突
        int k = 1;
        while(true){
            if ((V)data.key[hash] == null || ((V)data.key[hash]).equals(key))
                break;

            //线性探测再散列
            //hash = ++hash % M;

            //二次探测再散列
            hash = (hashbase + k*k*f) % M;
            if(f < 0) k++;
            f = -f;
        }

        return hash;
    }

    public void add(String key , V value){
        int hash = hashFun(key);
        data.key[hash] = key;
        data.value[hash] = value;
    }
    public void remove(String key){
        //开放定址法不能真正删除一个元素 只能设置一个删除标记
        int hash = hashFun(key);
        data.value[hash] = null;
        data.key[hash] = null;
    }
    public  V get(String key){
        return (V)data.value[hashFun(key)];
    }
    class Tab{
        public String[] key;
        public Object[] value;
        public Tab(){
            value = new Object[M];
            key = new String[M];
        }

    }
}